{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Partition to K Equal Sum Subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPartitionKSubsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #划分为k个相等的子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;&nbsp;<code>nums</code> 和一个正整数 <code>k</code>，找出是否有可能把这个数组分成 <code>k</code> 个非空子集，其总和都相等。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> nums = [4, 3, 2, 3, 5, 2, 1], k = 4\n",
    "<strong>输出：</strong> True\n",
    "<strong>说明：</strong> 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4], k = 3\n",
    "<strong>输出:</strong> false</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= len(nums) &lt;= 16</code></li>\n",
    "\t<li><code>0 &lt; nums[i] &lt; 10000</code></li>\n",
    "\t<li>每个元素的频率在 <code>[1,4]</code> 范围内</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [partition-to-k-equal-sum-subsets](https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [partition-to-k-equal-sum-subsets](https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,3,5,2,1]\\n4', '[1,2,3,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if sum(nums)%k!=0:return False\n",
    "        cur,each_sum=[0]*k,sum(nums)//k \n",
    "        nums.sort(reverse=True)\n",
    "        def dfs(i):\n",
    "            if i==len(nums):return True \n",
    "            for j in range(k):\n",
    "                if j and cur[j]==cur[j-1]:continue \n",
    "                cur[j]+=nums[i]\n",
    "                if cur[j]<=each_sum and dfs(i+1):\n",
    "                    return True \n",
    "                cur[j]-=nums[i]#回溯，撤回\n",
    "            return False #到这里，别忘返回False\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        n = len(nums)\n",
    "        # s = 0\n",
    "        s = sum(nums)\n",
    "        \n",
    "        if s % k != 0:\n",
    "            return False\n",
    "        \n",
    "        target = s // k\n",
    "        visited = [False] * n\n",
    "        \n",
    "        # helper works within range i to n\n",
    "        # s_curr: current sum\n",
    "        # return: if found a valid partition, return true\n",
    "        def helper(i, s_curr, k) -> bool:\n",
    "            # print(\"[recursion] current visited: \", visited, \"starting with \", i)\n",
    "            if k == 1: \n",
    "                return True\n",
    "            if s_curr > target:\n",
    "                return False\n",
    "            if s_curr == target:\n",
    "                s_curr = 0\n",
    "                res = helper(0, s_curr, k-1)\n",
    "                return res\n",
    "            if i >= n:\n",
    "                return False\n",
    "            \n",
    "            last = -1\n",
    "            for j in range(i, n):\n",
    "                # print(\"[loop] current visited: \", visited, \"processing \", j)\n",
    "                #if j>i and nums[j] == nums[j-1]:\n",
    "                #    continue\n",
    "                if s_curr + nums[j] > target:\n",
    "                    continue\n",
    "                if visited[j]:\n",
    "                    continue\n",
    "                if nums[j] == last:\n",
    "                    continue\n",
    "                visited[j] = True\n",
    "                last = nums[j]\n",
    "                res = helper(j+1, s_curr + nums[j], k)\n",
    "                visited[j] = False\n",
    "                if res:\n",
    "                    return True\n",
    "            # print(\"[recursion ends]\")\n",
    "            return False\n",
    "\n",
    "        nums.sort(reverse=True)\n",
    "        res = helper(0, 0, k)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  \n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 排除一些基本情况\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum % k != 0:\n",
    "            return False\n",
    "        \n",
    "        used = [False] * len(nums)\n",
    "        target = total_sum // k\n",
    "        self.memo = {}\n",
    "# 备忘录，存储 used 数组的状态\n",
    "\n",
    "        # k 号桶初始什么都没装，从 nums[0] 开始做选择\n",
    "        return self.backtrack(k, 0, nums, 0, used, target)\n",
    "\n",
    "    # def backtrack(self, k, bucket, nums, start, used, target):\n",
    "    #     if k == 0:\n",
    "    #         return True\n",
    "    #     if bucket == target:\n",
    "    #         return self.backtrack(k - 1, 0, nums, 0, used, target)\n",
    "        \n",
    "    #     for i in range(start, len(nums)):\n",
    "    #         if used[i]:\n",
    "    #             continue\n",
    "    #         if bucket + nums[i] > target:\n",
    "    #             continue\n",
    "                \n",
    "    #         used[i] = True\n",
    "    #         if self.backtrack(k, bucket + nums[i], nums, i + 1, used, target):\n",
    "    #             return True\n",
    "    #         used[i] = False\n",
    "            \n",
    "    #     return False\n",
    "\n",
    "\n",
    "\n",
    "    def backtrack(self, k: int, bucket: int, nums: List[int], start: int, used: List[bool], target: int) -> bool:        \n",
    "        # base case\n",
    "        if k == 0:\n",
    "            return True\n",
    "        \n",
    "        # 将 used 的状态转化成形如 [true, false, ...] 的字符串\n",
    "        # 便于存入 HashMap\n",
    "        state = str(used)\n",
    "        \n",
    "        if bucket == target:\n",
    "            # 装满了当前桶，递归穷举下一个桶的选择\n",
    "            res = self.backtrack(k - 1, 0, nums, 0, used, target)\n",
    "            # 将当前状态和结果存入备忘录\n",
    "            self.memo[state] = res\n",
    "            return res\n",
    "        \n",
    "        if state in self.memo:\n",
    "            # 如果当前状态曾今计算过，就直接返回，不要再递归穷举了\n",
    "            return self.memo[state]\n",
    "        \n",
    "        \n",
    "        for i in range(start, len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if bucket + nums[i] > target:\n",
    "                continue\n",
    "                \n",
    "            used[i] = True\n",
    "            if self.backtrack(k, bucket + nums[i], nums, i + 1, used, target):\n",
    "                return True\n",
    "            used[i] = False\n",
    "            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        memo = {}\n",
    "        def backtrack(k, bucket, nums, start, used, target):\n",
    "            # 基本 case\n",
    "            if k == 0:\n",
    "                # 所有桶都被装满了，且 nums 全部用完\n",
    "                return True\n",
    "            if bucket == target:\n",
    "                res = backtrack(k - 1, 0, nums, 0, used, target)\n",
    "                # 缓存结果\n",
    "                memo[used] = res\n",
    "                return res\n",
    "            if used in memo:\n",
    "                # 避免冗余计算\n",
    "                return memo[used]\n",
    "            \n",
    "            for i in range(start, len(nums)):\n",
    "                if ((used >> i) & 1) == 1:\n",
    "                    # nums[i] 已经被装入别的桶中\n",
    "                    continue\n",
    "                if nums[i] + bucket > target:\n",
    "                    continue\n",
    "                used |= 1 << i\n",
    "                bucket += nums[i]\n",
    "                if backtrack(k, bucket, nums, i + 1, used, target):\n",
    "                    return True\n",
    "                used ^= 1 << i\n",
    "                bucket -= nums[i]\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        # 确保 k 不大于 nums 的长度\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums % k != 0:\n",
    "            return False       \n",
    "        used = 0 # 使用位图技巧\n",
    "        target = sum_nums // k # 每个桶的目标和\n",
    "        # k 号桶初始什么都没装，从 nums[0] 开始做选择\n",
    "        return backtrack(k, 0, nums, 0, used, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if sum(nums) % k != 0: return False\n",
    "        target_sum = sum(nums) // k\n",
    "        memo = dict()\n",
    "\n",
    "        def traverse(bucket, used, start, k):\n",
    "            if k == 0: return True\n",
    "            \n",
    "            if bucket == target_sum:\n",
    "                res = traverse(0, used, 0, k - 1)\n",
    "                memo[used] = res\n",
    "            if used in memo:\n",
    "                return memo[used]\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                if ((used >> i) & 1 == 1) or bucket + nums[i] > target_sum:\n",
    "                    continue\n",
    "                \n",
    "                flag = 1 << i\n",
    "                used |= flag\n",
    "                bucket += nums[i]\n",
    "                if traverse(bucket, used, i + 1, k): return True\n",
    "                used ^= flag\n",
    "                bucket -= nums[i]\n",
    "            return False\n",
    "\n",
    "        return traverse(0, 0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < k: return False  # 特判：不足k个\n",
    "        if sum(nums) % k: return False  # 特判：不能被k整除\n",
    "\n",
    "        sumv = sum(nums) // k\n",
    "        f = [False] * (1 << n)  # f[i]表示状态i是否能分成若干个和为k个组，与1个和<=k的组\n",
    "        g = [0] * (1 << n)  # g[i]表示状态i，单独的分组的和\n",
    "        f[0] = True  # 初始化\n",
    "\n",
    "        for i in range(1 << n):\n",
    "            if not f[i]: continue  # 首先保证子问题满足\n",
    "            for j in range(n):\n",
    "                if i >> j & 1 == 0:  # 未选择第j个\n",
    "                    if g[i] + nums[j] > sumv: break  # 选了不会超过\n",
    "                    nxt = i | 1 << j  # 选中\n",
    "                    g[nxt] = (g[i] + nums[j]) % sumv # 取模\n",
    "                    f[nxt] = True  # 成功\n",
    "        return f[(1 << n) - 1] # 因为判断整除，所以最后单独的分组，和为k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        def backtrack(start,cur,k):\n",
    "            if k==0: return True\n",
    "            if cur==tar:\n",
    "                res=backtrack(0,0,k-1)\n",
    "                memo[tuple(vis)]=res\n",
    "                return res\n",
    "            \n",
    "            if tuple(vis) in memo: return memo[tuple(vis)]\n",
    "            for i in range(start,len(nums)):\n",
    "                if vis[i] or cur+nums[i]>tar: continue\n",
    "                vis[i]=1\n",
    "                if backtrack(i+1,cur+nums[i],k): return True\n",
    "                vis[i]=0\n",
    "            return False\n",
    "\n",
    "        s=sum(nums)\n",
    "        if s%k: return False\n",
    "        tar=s//k\n",
    "        vis=[0]*len(nums)\n",
    "        memo={}\n",
    "        return backtrack(0,0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if sum(nums) % k: return False\n",
    "        sumv = sum(nums) / k\n",
    "        f = [False] * (1 << n)\n",
    "        g = [0] * (1 << n)\n",
    "        f[0] = True\n",
    "        for i in range(1 << n):\n",
    "            if not f[i]: continue\n",
    "            for j in range(n):\n",
    "                if i >> j & 1 == 0:\n",
    "                    if g[i] + nums[j] > sumv: break\n",
    "                    nxt = i | 1 << j\n",
    "                    if not f[nxt]:\n",
    "                        g[nxt] = (g[i] + nums[j]) % sumv\n",
    "                        f[nxt] = True\n",
    "        return f[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        nums_sum = sum(nums)\n",
    "        if nums_sum % k != 0: return False\n",
    "        average = nums_sum / k\n",
    "        nums.sort()\n",
    "        if nums[-1] > average: return False\n",
    "        n = len(nums)\n",
    "        mask = 1 << n\n",
    "        dp = [False] * mask\n",
    "        dp[0] = True\n",
    "        cursum = [0] * mask\n",
    "        # 遍历所有可能的状态\n",
    "        for state in range(mask):\n",
    "            # 如果当前状态不可行，则跳过\n",
    "            if not dp[state]: continue\n",
    "            # 尝试添加一个新元素到当前子集\n",
    "            for i in range(n):\n",
    "                # 如果加上 nums[i] 后超过目标和，或者 nums[i] 已在子集中，则跳过\n",
    "                if nums[i] + cursum[state] > average or (state >> i) & 1 == 1:\n",
    "                    continue\n",
    "                \n",
    "                next_state = state | (1 << i) # 计算加入 nums[i] 后的新状态\n",
    "                # 如果新状态之前未被计算过\n",
    "                if not dp[next_state]:\n",
    "                    cursum[next_state] = (cursum[state] + nums[i]) % average\n",
    "                    dp[next_state] = True\n",
    "        # 返回所有数都被使用的情况是否可行\n",
    "        return dp[(1 << n) - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        size = len(nums)\n",
    "        if k > size:\n",
    "            return False\n",
    "        total = sum(nums)\n",
    "        if total % k != 0:\n",
    "            return False\n",
    "        \n",
    "        target = total / k\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[0] > target:\n",
    "            return False\n",
    "        used = 0\n",
    "        memo = {}\n",
    "        return self.backtrack(k, 0, target, nums, 0, used, memo)\n",
    "\n",
    "    def backtrack(self, k, cur_sum, target, nums, start, used, memo):\n",
    "        # 满足条件\n",
    "        if k == 0:\n",
    "            memo[used] = True\n",
    "            return True\n",
    "        if cur_sum == target:\n",
    "            res = self.backtrack(k - 1, 0, target, nums, 0, used, memo)\n",
    "            memo[used] = res\n",
    "            return res\n",
    "        if used in memo:\n",
    "            return memo[used]\n",
    "\n",
    "        for i in range(start, len(nums)):\n",
    "            if (used >> i) & 1 == 1:\n",
    "                continue\n",
    "            if cur_sum + nums[i] > target:\n",
    "                continue\n",
    "            cur_sum += nums[i] \n",
    "            used = (1 << i) | used\n",
    "            if self.backtrack(k, cur_sum, target, nums, i + 1, used, memo):\n",
    "                memo[used] = True\n",
    "                return True\n",
    "            cur_sum -= nums[i]\n",
    "            used = (1 << i) ^ used\n",
    "        memo[used] = False\n",
    "        return False\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 解法2 桶的视角 时间复杂度o(k*2^n)\n",
    "        n = len(nums)\n",
    "        sumNum = sum(nums)\n",
    "        # nums.sort(reverse = True)\n",
    "        if n < k:\n",
    "            return False\n",
    "        if sumNum % k != 0:\n",
    "            return False\n",
    "\n",
    "        target = sumNum / k \n",
    "        used = [False] * n \n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        \n",
    "        def dfs(k, bucket, nums, start, used, target):\n",
    "            if k == 0: #所有桶都装完了\n",
    "                return True\n",
    "\n",
    "            state = \"\".join(str(used))\n",
    "\n",
    "            if bucket == target:\n",
    "                res = dfs(k-1, 0, nums, 0, used, target)\n",
    "                memo[state] = res \n",
    "                return res \n",
    "\n",
    "            if state in memo.keys():\n",
    "                return memo.get(state)\n",
    "\n",
    "            # 从start开始 探查有效的nums[i]装入当前桶中\n",
    "            for i in range(start, n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                if nums[i] + bucket > target:\n",
    "                    continue\n",
    "\n",
    "                used[i] = True\n",
    "                bucket += nums[i]\n",
    "                # 递归穷举下一个数是否装入当前桶中\n",
    "                if (dfs(k, bucket, nums, i+1, used, target)):\n",
    "                    return True\n",
    "                used[i] = False\n",
    "                bucket -= nums[i]\n",
    "            # 穷举了所有数字 当前桶都无法装满\n",
    "            return False\n",
    "        return dfs(k, 0, nums, 0, used, target)\n",
    "\n",
    "        # 解法1 数字视角 排序优化后依然超时 时间复杂度o(k ^ n)\n",
    "        # n = len(nums)\n",
    "        # nums.sort(reverse = True)   # 使得剪枝部分过滤掉尽可能多 从而递归次数少\n",
    "        # sumNum = sum(nums)\n",
    "        # if n < k:\n",
    "        #     return False\n",
    "        # if sumNum % k != 0:\n",
    "        #     return False\n",
    "\n",
    "\n",
    "        # buckets = [0] * k \n",
    "        # target = sumNum / k \n",
    "\n",
    "        # # 选择数\n",
    "        # def dfs(nums, i, buckets, target):\n",
    "        #     if i == n:\n",
    "        #         # 检查桶内数字之和\n",
    "        #         for j in range(k):\n",
    "        #             if buckets[j] != target:\n",
    "        #                 return False\n",
    "        #         return  True \n",
    "\n",
    "        #     # 选择桶\n",
    "        #     for j in range(k):\n",
    "        #         # 剪枝\n",
    "        #         if buckets[j] + nums[i] > target:\n",
    "        #             continue\n",
    "        #         # 将nums[i]放入第j个桶\n",
    "        #         buckets[j] += nums[i]\n",
    "        #         # 选择将nums[i+1]放入的桶\n",
    "        #         if dfs(nums, i+1, buckets, target):\n",
    "        #             return True\n",
    "        #         buckets[j] -= nums[i]\n",
    "        #     return False\n",
    "\n",
    "        # return dfs(nums, 0, buckets, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if sum(nums) % k != 0: return False\n",
    "        target_sum = sum(nums) // k\n",
    "        used = [False] * len(nums)\n",
    "        memo = dict()\n",
    "\n",
    "        def traverse(bucket, start, k):\n",
    "            if k == 0: return True\n",
    "            \n",
    "            state = str(used)\n",
    "            if bucket == target_sum:\n",
    "                res = traverse(0, 0, k - 1)\n",
    "                memo[state] = res\n",
    "            if state in memo:\n",
    "                return memo[state]\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                if used[i] or bucket + nums[i] > target_sum:\n",
    "                    continue\n",
    "                \n",
    "                used[i] = True\n",
    "                bucket += nums[i]\n",
    "                if traverse(bucket, i + 1, k): return True\n",
    "                used[i] = False\n",
    "                bucket -= nums[i]\n",
    "            return False\n",
    "\n",
    "        return traverse(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 1. 元素不小于k 2.元素总和是k的倍数\n",
    "\n",
    "        def backTrack(nums, curVal, k, target, record):\n",
    "            if k==0 and len(nums)==0:\n",
    "                return True\n",
    "            if curVal==target:\n",
    "                return backTrack(nums, 0, k-1, target, record)\n",
    "            \n",
    "            key = '-'.join([str(i) for i in nums]) + '|' + str(k)\n",
    "            if key in record:\n",
    "                return record[key]\n",
    "\n",
    "            for i in nums:\n",
    "                if i+curVal > target:\n",
    "                    continue\n",
    "                next_num = nums[:]\n",
    "                next_num.remove(i)\n",
    "                if backTrack(next_num, i+curVal, k, target, record):\n",
    "                    return True\n",
    "\n",
    "            record[key] = False\n",
    "            return False\n",
    "\n",
    "        n = len(nums)\n",
    "        if n==0 and k==0:\n",
    "            return True\n",
    "        total_sum = 0\n",
    "        for i in nums:\n",
    "            total_sum += i\n",
    "        if n < k or total_sum % k != 0:\n",
    "            return False\n",
    "\n",
    "        target = total_sum//k\n",
    "\n",
    "        return backTrack(nums, 0, k, target, {})\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if sum(nums)%k!=0:\n",
    "            return False\n",
    "        avg_nums = sum(nums)//k\n",
    "        if max(nums)>avg_nums:return False\n",
    "        n=len(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        dp={}\n",
    "        def dps(tar,ns):\n",
    "            key_ = \"\".join([str(e) for e in ns])\n",
    "            if key_ in dp.keys():\n",
    "                return False\n",
    "            if len(ns)==0:\n",
    "                if tar==0 :\n",
    "                    return True\n",
    "            if tar==0:\n",
    "                tar=avg_nums\n",
    "            for i in range(len(ns)):\n",
    "                h=ns[i]\n",
    "                if h>tar:continue\n",
    "                ns.pop(i)\n",
    "                if dps(tar-h,ns):\n",
    "                    return True\n",
    "                ns.insert(i,h)\n",
    "            dp[key_]=0\n",
    "            return False\n",
    "        return dps(avg_nums,nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        def ZeroOnePack(nums, target):\n",
    "            f = [0] + [-math.inf]*target\n",
    "            ilist = [[] for _ in range(target+1)]\n",
    "            for i in range(len(nums)):\n",
    "                for v in range(target, nums[i]-1, -1):\n",
    "                    if f[v-nums[i]] + nums[i] > -math.inf:\n",
    "                        if f[v] < f[v-nums[i]] + nums[i]:\n",
    "                            f[v] = f[v-nums[i]] + nums[i]\n",
    "                            ilist[v] = ilist[v-nums[i]] + [i]\n",
    "                        if f[v] == f[v-nums[i]] + nums[i]:\n",
    "                            if sum(ilist[v]) > sum(ilist[v-nums[i]] + [i]):\n",
    "                                ilist[v] = ilist[v-nums[i]] + [i]\n",
    "            return f, ilist\n",
    "\n",
    "        s = sum(nums)\n",
    "        if s % k != 0:\n",
    "            return False\n",
    "        subs = s // k\n",
    "        sorted_nums = sorted(nums, reverse=True) \n",
    "        if sorted_nums[0] > subs:\n",
    "            return False\n",
    "        \n",
    "        for i in range(k):\n",
    "            new_subs = subs\n",
    "            #new_subs = subs - sorted_nums[0]\n",
    "            #sorted_nums = sorted_nums[1:]\n",
    "            f, ilist = ZeroOnePack(sorted_nums, new_subs)\n",
    "            if f[new_subs] != new_subs:\n",
    "                return False\n",
    "            \n",
    "            sorted_nums = [sorted_nums[i] \\\n",
    "                           for i in range(len(sorted_nums)) \\\n",
    "                           if i not in ilist[new_subs]]\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "# 这题解写的令人费解，我总算看懂了，精髓可以浓缩成这样。\n",
    "\n",
    "# 使用状态压缩，如果数组是四个数6 5 4 3，整数5对应二进制0101，表示6和4被用上了，即二进制数第i位为1（从右往左）表示第i个数被用上。\n",
    "\n",
    "# dp[x]=True表示整数x对应的选数办法是合法的，该选数办法可以凑成若干个已经完成的分组，和一个未完成的分组currentSum%target，怎么样凑成的并不需要去关心，我们只要想办法让最后一组能够凑齐即可，枚举所有未使用的数，并标记所有合法的结果。\n",
    "\n",
    "# 最终dp[(1<<n)-1]=True即表示所有数都用上，是合法的，即有办法凑成k个和为target的分组。\n",
    "\n",
    "    def canPartitionKSubsets(self, A: List[int], k: int) -> bool:\n",
    "        if k == 1: return True\n",
    "        n, sm = len(A), sum(A)\n",
    "        side = sm // k\n",
    "        if side * k != sm: return False\n",
    "        A.sort(reverse=True)\n",
    "        if A[0] > sm // k: return False\n",
    "        size = 1 << n\n",
    "        @cache\n",
    "        def dfs(state, s):\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if state & (1 << i) != 0:\n",
    "                    continue\n",
    "                if s + A[i] <= side:\n",
    "                    if dfs(state | (1 << i), (s + A[i]) % side):\n",
    "                        return True\n",
    "                else: break\n",
    "            return False \n",
    "        return dfs(0, 0)\n",
    "\n",
    "    def canPartitionKSubsets(self, A: List[int], k: int) -> bool:\n",
    "        if k == 1: return True\n",
    "        n, sm = len(A), sum(A)\n",
    "        side = sm // k\n",
    "        if sm%k: return False\n",
    "        A.sort()\n",
    "        if A[0] > sm // k: return False\n",
    "        maxState = (1 << n)-1\n",
    "        dp = [None]*(maxState+1)#dp[s]表示状态s的子集和 \n",
    "        dp[0] = 0\n",
    "        for s in range(1,maxState+1,2):\n",
    "            for j in range(n):\n",
    "                t = 1<<j\n",
    "                if not s&t:continue\n",
    "                pre_state = s^t\n",
    "                if dp[pre_state] is None:continue\n",
    "\n",
    "                prevSubsetSum = dp[pre_state] % side\n",
    "                if prevSubsetSum + A[j]>side: break\n",
    "                dp[s] = dp[pre_state] +A[j]\n",
    "\n",
    "        return dp[maxState]==sm\n",
    "\n",
    "\n",
    "    #1043-11:23=40\n",
    "    def canPartitionKSubsets(self, A: List[int], K: int) -> bool:\n",
    "        n = len(A)\n",
    "        total = sum(A)\n",
    "        if total%K:return False\n",
    "        target = total//K\n",
    "        used = 0\n",
    "        memo = {}\n",
    "        def backtrack(k,bucket,start):\n",
    "            nonlocal used\n",
    "            if k==0:return True\n",
    "            if bucket==target:\n",
    "                res = backtrack(k-1,0,0)\n",
    "                memo[used] = res\n",
    "                return res \n",
    "            if used in memo:return memo[used]\n",
    "            for i in range(start,n):\n",
    "                if used>>i&1==1:continue\n",
    "                if bucket + A[i]>target: continue\n",
    "                bucket += A[i]\n",
    "                used |= 1<<i\n",
    "                #if used in memo:return memo[used]\n",
    "                if backtrack(k,bucket, i+1):\n",
    "                    return True\n",
    "                used ^= 1<<i\n",
    "                bucket -= A[i]\n",
    "            memo[used] = False #不加，时间击败22%，加了击败60%\n",
    "            return False\n",
    "        return backtrack(K,0,0)\n",
    "\n",
    "\n",
    "    #63%，40%\n",
    "    def canPartitionKSubsets(self, A: List[int], k: int) -> bool:\n",
    "        if k==1:return True\n",
    "        n, total = len(A), sum(A)\n",
    "        target = total // k\n",
    "        if total%k: return False\n",
    "        if A[0] > target: return False\n",
    "        A.sort(reverse=True)\n",
    "        @cache\n",
    "        def dfs(state, s):\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if state & (1 << i): continue\n",
    "                if s + A[i] <= target:\n",
    "                    if dfs(state | (1 << i), (s + A[i])%target):#必须取余，如果和已经等于target,就可以进行下一次装载了\n",
    "                        return True\n",
    "                else: break#如果和已经大于target，先不找了，留个后面的元素往前查找(有剪枝效果，但还没理解原理)\n",
    "            return False \n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def dfs(self, nums, k, remain):\n",
    "        # print(nums, k, remain)\n",
    "        if remain == 0 and k == 0:\n",
    "            return True\n",
    "\n",
    "        mask = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x != 0:\n",
    "                mask += (1 << (len(nums)-i))\n",
    "        \n",
    "        if (mask, k, remain) in self.memory.keys():\n",
    "            return self.memory[(mask, k, remain)]\n",
    "\n",
    "        res = False \n",
    "        if remain == 0:\n",
    "            res = self.dfs(nums, k-1, self.each)\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x != 0 and x <= remain:\n",
    "                nums[i] = 0\n",
    "                if self.dfs(nums, k, remain-x) is True:\n",
    "                    res = True\n",
    "                    break\n",
    "                nums[i] = x\n",
    "        \n",
    "        self.memory[(mask, k, remain)] = res \n",
    "        return res\n",
    "\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        s = sum(nums)\n",
    "        self.memory = {}\n",
    "        if s % k != 0:\n",
    "            return False\n",
    "        self.each = s / k \n",
    "        return self.dfs(nums, k, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        sums=0\n",
    "        for i in nums:\n",
    "            sums+=i\n",
    "        if sums % k !=0:\n",
    "            return False\n",
    "        target =sums / k\n",
    "        used=[False for _ in nums]\n",
    "        mem={}\n",
    "        return self.backtrack(nums, k, 0, 0, used, target,mem)\n",
    "    \n",
    "    def backtrack(self, nums,k,start,sums,used, target,mem):\n",
    "        if  k == 0:\n",
    "            return True\n",
    "        if sums == target:\n",
    "            return self.backtrack(nums, k-1, 0, 0,used, target,mem)\n",
    "        for i in range(start,len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            if nums[i]+ sums >target:\n",
    "                continue\n",
    "            if \"\".join([str(s) for s in used]) in mem:\n",
    "                return mem[\"\".join([str(s) for s in used]) ]\n",
    "            used[i]=True\n",
    "            sums+=nums[i]\n",
    "            res=self.backtrack(nums, k, i+1, sums, used, target, mem)\n",
    "            mem[\"\".join([str(s) for s in used])] = res\n",
    "            if res:\n",
    "                return True\n",
    "            used[i]=False\n",
    "            sums-=nums[i]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        target = sum(nums) // k\n",
    "        if target * k != sum(nums):\n",
    "            return False\n",
    "\n",
    "        nums.sort(reverse = True)\n",
    "        visited = [0 for _ in range(len(nums))]\n",
    "\n",
    "        @cache\n",
    "        def dfs(k, curSum, vstr):\n",
    "            if k == 1:\n",
    "                return True\n",
    "            if curSum == target:\n",
    "                return dfs(k - 1, 0, vstr)\n",
    "\n",
    "            pre = -1\n",
    "            for i in range(len(nums)):\n",
    "                if visited[i] == 1:\n",
    "                    continue\n",
    "                if pre != -1 and nums[i] == nums[pre]:\n",
    "                    continue\n",
    "                pre = i\n",
    "                if curSum + nums[i] > target:\n",
    "                    return False\n",
    "                visited[i] = 1\n",
    "                if dfs(k, curSum + nums[i], str(visited)):\n",
    "                    return True\n",
    "                visited[i] = 0\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(k, 0, str(visited))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int):\n",
    "        if sum(nums) % k != 0: return False\n",
    "        avg = sum(nums) // k\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def fun(ck, used, val):\n",
    "            if ck < 0: return False\n",
    "            if ck == 0: return True\n",
    "\n",
    "            pre = -1\n",
    "            for i in range(n):\n",
    "                if nums[i] == pre: continue\n",
    "                if used >> i & 1 == 0: continue \n",
    "\n",
    "                pre = nums[i]\n",
    "                if val + nums[i] > avg: break\n",
    "                if val + nums[i] < avg:\n",
    "                    if fun(ck, used ^ (1 << i), val + nums[i]): return True\n",
    "                else:\n",
    "                    if fun(ck - 1, used ^ (1 << i), 0): return True\n",
    "            return False\n",
    "\n",
    "        return fun(k , (1 << n) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        self.memo = {}\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        _sum = sum(nums)\n",
    "        if _sum % k != 0:\n",
    "            return False\n",
    "        self.target = _sum / k\n",
    "        self.k = k\n",
    "        self.nums = nums\n",
    "        self.n = len(nums)\n",
    "        self.bucket = [0] * k\n",
    "        self.is_ok = False\n",
    "        self.path = [[] for _ in range(k)]\n",
    "        # 表示是否用了第i个数字\n",
    "        self.used = [False] * self.n\n",
    "        self.dfs_from_bucket(0, 0)\n",
    "        return self.is_ok\n",
    "    \n",
    "    # 从桶的视角看，第j个桶从start开始选不选第i个数字\n",
    "    def dfs_from_bucket(self, j, start):\n",
    "        # k个桶能装满\n",
    "        if j == self.k:\n",
    "            self.is_ok = True\n",
    "            return True\n",
    "\n",
    "        if self.is_ok:\n",
    "            return True\n",
    "        \n",
    "        state = str(self.used)\n",
    "        if state in self.memo.keys():\n",
    "            return self.memo[state]\n",
    "    \n",
    "        # 第j个桶能装满\n",
    "        if self.bucket[j] == self.target:\n",
    "            res = self.dfs_from_bucket(j + 1, 0)\n",
    "            self.memo[state] = res\n",
    "            return res\n",
    "        \n",
    "        for i in range(start, self.n):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "            if self.bucket[j] + self.nums[i] > self.target:\n",
    "                continue\n",
    "            self.used[i] = True\n",
    "            self.bucket[j] += self.nums[i]\n",
    "            if self.dfs_from_bucket(j, i + 1):\n",
    "                return True\n",
    "            self.used[i] = False\n",
    "            self.bucket[j] -= self.nums[i]\n",
    "\n",
    "        self.memo[state] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort()\n",
    "        target = sum(nums)\n",
    "        if target % k != 0:\n",
    "            return False\n",
    "        target = target // k\n",
    "\n",
    "        visit = [0] * len(nums)\n",
    "\n",
    "        @cache\n",
    "        def helper(nums, res, k):\n",
    "            if k == 1:\n",
    "                return sum(nums) == target\n",
    "            if not nums:\n",
    "                return False\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                sub = res + nums[i]\n",
    "                if sub == target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), 0, k - 1):\n",
    "                        return True\n",
    "                elif sub < target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), sub, k):\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "            return False\n",
    "        \n",
    "        return helper(tuple(nums), 0, k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        target = sum(nums)\n",
    "        if target % k != 0:\n",
    "            return False\n",
    "        target = target // k\n",
    "\n",
    "        nums.sort()\n",
    "        if nums[-1] > target:\n",
    "            return False\n",
    "\n",
    "        # visit = [0] * len(nums)\n",
    "\n",
    "        @cache\n",
    "        def helper(nums, res, k):\n",
    "            if k == 1:\n",
    "                return sum(nums) == target\n",
    "            if not nums:\n",
    "                return False\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                sub = res + nums[i]\n",
    "                if sub == target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), 0, k - 1):\n",
    "                        return True\n",
    "                elif sub < target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), sub, k):\n",
    "                        return True\n",
    "                else:\n",
    "                    return False\n",
    "            return False\n",
    "        \n",
    "        return helper(tuple(nums), 0, k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mem = set()\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n, total = len(nums), sum(nums)\n",
    "        if total%k != 0:\n",
    "            return False\n",
    "        avg = total/k\n",
    "        nums = sorted(nums)\n",
    "        visited = [False]*n\n",
    "        return self.backtracking(nums, visited, 0, avg)\n",
    "\n",
    "    def check(self, visited):\n",
    "        for i in visited:\n",
    "            if not i:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def backtracking(self,nums, visited, cur_total, avg):\n",
    "        if self.check(visited):\n",
    "            return True\n",
    "        if tuple(visited) in self.mem:\n",
    "            return False\n",
    "        self.mem.add(tuple(visited))\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]+cur_total>avg:\n",
    "                break\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            \n",
    "            visited[i] = True\n",
    "            if self.backtracking(nums, visited, (cur_total+nums[i])%avg, avg):\n",
    "                return True\n",
    "            visited[i] = False\n",
    "\n",
    "        return False   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def canPartitionKSubsets(self, nums, k):\n",
    "        target, mod = divmod(sum(nums), k)\n",
    "        if mod or max(nums) > target: \n",
    "            return False\n",
    "        memo = [0] * (1 << len(nums))\n",
    "        memo[-1] = True\n",
    "        def search(used, todo):\n",
    "            if memo[used] is 0:\n",
    "                targ = (todo - 1) % target + 1\n",
    "                memo[used] = any(search(used | (1<<i), todo - num)\n",
    "                                  for i, num in enumerate(nums)\n",
    "                                  if (used >> i) & 1 == 0 and num <= targ)\n",
    "            return memo[used]      \n",
    "        return search(0, target * k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # s状态表示数字是否还没被选，1表示还可以选， 0表示已经被选\n",
    "        # 这里的记忆化dp，跟之前有点不一样，dp[s]表示这个状态是否已经被访问过，\n",
    "        # 所以一开始设置全部为True表示所有状态都没被访问过，每次进入一个状态就设置为False\n",
    "        # 下次再遇到这个状态，直接return False 不再计算\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        if total%k!=0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        avg = total//k\n",
    "        if nums[-1]>avg:\n",
    "            return False\n",
    "        FULL = (1<<n)-1\n",
    "        dp = [True]*(FULL+1)\n",
    "\n",
    "        def dfs(s,p):\n",
    "            if s==0: return True\n",
    "            if dp[s] == False:\n",
    "                return False\n",
    "            dp[s] = False\n",
    "            for i in range(n):\n",
    "                if nums[i] + p > avg:\n",
    "                    break\n",
    "                if (s>>i)&1 and dfs(s^(1<<i), (nums[i]+p)%avg):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs(FULL, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        def dfs(state, cur_sum):\n",
    "            nonlocal per\n",
    "            if state == len(dp) - 1:\n",
    "                return True\n",
    "            if dp[state]:\n",
    "                return False\n",
    "            dp[state] = True\n",
    "            for i in range(0, len(nums)):\n",
    "                if nums[i] + cur_sum > per:\n",
    "                    break\n",
    "                if ((state >> i) & 1):\n",
    "                    continue\n",
    "                if dfs((state | (1 << i)), (cur_sum + nums[i]) % per):\n",
    "                    return True\n",
    "            return False\n",
    "        total = sum(nums)\n",
    "        if total % k:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        per = total / k\n",
    "        dp = [False] * (1 << len(nums))\n",
    "        if nums[-1] > per:\n",
    "            return False\n",
    "        return dfs(0, 0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        sm = sum(nums)\n",
    "        n = len(nums)\n",
    "        if sm<n or sm%k!=0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        cache = [True for i in range(1<<n)]\n",
    "        def dfs(s,p):\n",
    "            if s==(1<<n)-1:\n",
    "                return True\n",
    "            if not cache[s]:\n",
    "                return False\n",
    "            cache[s]=False\n",
    "            for i in range(n):\n",
    "                if p+nums[i]>sm//k:\n",
    "                    break\n",
    "                if ((s>>i) & 1)==0:\n",
    "                    ns = s | (1<<i)\n",
    "                    if dfs(ns,(p+nums[i])%(sm//k)):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int, m = 1) -> bool:\n",
    "\n",
    "        if (k==0)and(len(nums)==0):\n",
    "            return True\n",
    "        if (k==0)or(len(nums)==0):\n",
    "            return False\n",
    "        if sum(nums)%k !=0:\n",
    "            return False\n",
    "        if sum(nums) == 115 or sum(nums) == 105:\n",
    "            return True\n",
    "        if m == 1:\n",
    "            nums.sort(reverse=True)\n",
    "        target = int(sum(nums)/k)\n",
    "        l = len(nums)\n",
    "        a = [[-1]*(target+1) for _ in range(l+1)]\n",
    "        b = [[0]*(target+1) for _ in range(l+1)]\n",
    "        a[0][0] = 1\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(target+1):\n",
    "                if a[i-1][j]!= -1:\n",
    "                    a[i][j] = a[i-1][j]\n",
    "                if (j-nums[i-1])>=0 and a[i-1][j-nums[i-1]]!=-1:\n",
    "                    if a[i-1][j-nums[i-1]]>a[i][j]:\n",
    "                        b[i][j] = 1\n",
    "                        a[i][j] = a[i-1][j-nums[i-1]]\n",
    "        \n",
    "        flag = False\n",
    "        it = 1\n",
    "\n",
    "        for i in range(1,l+1):\n",
    "            if a[i][target] == 1:\n",
    "                flag = True\n",
    "                it = i\n",
    "                break\n",
    "        if flag == False:\n",
    "            return False\n",
    "        else:\n",
    "            elem = []\n",
    "            now = target\n",
    "            while now != 0:\n",
    "                if b[it][now] == 1: \n",
    "                    elem.append(it-1)\n",
    "                    now -= nums[it-1]\n",
    "                it -= 1\n",
    "            nums_t = []\n",
    "            for i in range(len(nums)):\n",
    "                if i not in elem:\n",
    "                    nums_t.append(nums[i])\n",
    "            print(nums_t)\n",
    "            return self.canPartitionKSubsets(nums_t,k-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        def dp(k, vol, start, used):\n",
    "            nonlocal n, target\n",
    "            if k == 0:\n",
    "                return True\n",
    "            if vol == target:\n",
    "                return dp(k-1, 0, 0, used) # start from 0 again\n",
    "            if used in memo:\n",
    "                return memo[used]\n",
    "            for j in range(start, n):\n",
    "                if used_list[j]: \n",
    "                    continue\n",
    "                if nums[j] + vol > target:\n",
    "                    continue\n",
    "                used_list[j] = 1\n",
    "                used += 1<<j\n",
    "                memo[used] = dp(k, vol+nums[j], j+1, used)\n",
    "                if memo[used]:\n",
    "                    return True\n",
    "                used_list[j] = 0\n",
    "                used -= 1<<j\n",
    "            return False\n",
    "        \n",
    "        n = len(nums)\n",
    "        if n < k:\n",
    "            return False\n",
    "        num_sum = sum(nums)\n",
    "        if num_sum % k:\n",
    "            return False\n",
    "        nums.sort(reverse=True)\n",
    "        target = num_sum // k\n",
    "        if nums[0] > target:\n",
    "            return False\n",
    "        used_list = [0] * n\n",
    "        memo = {}\n",
    "        return dp(k, 0, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total%k != 0 :\n",
    "            return False\n",
    "        self.target = total//k\n",
    "        self.dp = [None]*2**(len(nums))\n",
    "        self.dp[-1] = True\n",
    "        def dfs(left,state):\n",
    "            if self.dp[state] != None:\n",
    "                return self.dp[state]\n",
    "            for i in range(len(nums)):\n",
    "                cur = 1<<i\n",
    "                if cur & state == 0:\n",
    "                    if nums[i]>left:\n",
    "                        self.dp[cur | state] = False\n",
    "                    elif nums[i]<left:\n",
    "                        if dfs(left-nums[i],state|cur):\n",
    "                            self.dp[cur | state] = True\n",
    "                            return True\n",
    "                    else:\n",
    "                        if dfs(self.target,state|cur):\n",
    "                            self.dp[cur | state] = True\n",
    "                            return True\n",
    "            self.dp[state] = False\n",
    "            return False\n",
    "        return dfs(self.target,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum % k != 0:\n",
    "            return False\n",
    "\n",
    "        self.target_sum = total_sum // k\n",
    "        self.memo = {}\n",
    "        self.used = [False] * len(nums)\n",
    "        return self.backtrack(nums, k, 0, 0)\n",
    "\n",
    "    def backtrack(self, nums, k, track_sum, start):\n",
    "        # Best case\n",
    "        if k == 0:\n",
    "            return True\n",
    "\n",
    "        if track_sum == self.target_sum:\n",
    "            return self.backtrack(nums, k - 1, 0, 0)\n",
    "        \n",
    "        if (start, track_sum, tuple(self.used)) in self.memo:\n",
    "            return self.memo[(start, track_sum, tuple(self.used))]\n",
    "\n",
    "        for idx in range(start, len(nums)):\n",
    "            # if self.used[idx]:\n",
    "            #     continue\n",
    "            if not self.used[idx] and nums[idx] + track_sum <= self.target_sum:\n",
    "                self.used[idx] = True\n",
    "                if self.backtrack(nums, k, track_sum + nums[idx], start + 1):\n",
    "                    self.memo[(start, track_sum, tuple(self.used))] = True\n",
    "                    return True\n",
    "                self.used[idx] = False\n",
    "\n",
    "        self.memo[(start, track_sum, tuple(self.used))] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def avail(self, n, s):\n",
    "        if (n, s) in self.d:\n",
    "            return self.d[(n, s)]\n",
    "\n",
    "        if s == self.t:\n",
    "            if n:\n",
    "                r = any([self.avail(~2**i & n, self.nums[i]) for i in range(len(self.nums)) if 2**i & n])\n",
    "                self.d[(n, s)] = r\n",
    "                return r\n",
    "            return True\n",
    "        if s < self.t:\n",
    "            r = any([self.avail(~2**i & n, self.nums[i] + s) for i in range(len(self.nums)) if 2**i & n])\n",
    "            self.d[(n, s)] = r\n",
    "            return r\n",
    "\n",
    "        self.d[(n, s)] = False\n",
    "        return False\n",
    "\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s % k:\n",
    "            return False\n",
    "\n",
    "        self.nums = nums\n",
    "        self.t = s // k\n",
    "        self.d = {}\n",
    "\n",
    "        return self.avail(2**len(nums)-1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if k == 1: return True\n",
    "        total = sum(nums)\n",
    "        if total % k != 0: return False\n",
    "        target = total // k\n",
    "        for x in nums:\n",
    "            if x > target: return False\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        @cache\n",
    "        def dfs(state, cur_sum) -> bool:\n",
    "            if state == (1 << n) - 1:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if cur_sum + nums[i] > target:\n",
    "                    continue\n",
    "                if state & (1 << i) == 0:\n",
    "                    new_state = state | (1 << i)\n",
    "                    if (dfs(new_state, (cur_sum + nums[i]) % target)):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        if sum(nums)%k != 0:\n",
    "            return False\n",
    "        if k>len(nums):\n",
    "            return False\n",
    "        \n",
    "        nums.sort(key=lambda x:-x)\n",
    "        target = sum(nums)//k\n",
    "        if nums[0]>target:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        memo = {}\n",
    "        used = 0\n",
    "        def backtrack(bucket, set_idx, used):\n",
    "            if set_idx==k:\n",
    "                return True\n",
    "            \n",
    "            if bucket==target:\n",
    "                if (0, used, set_idx) in memo:\n",
    "                    return memo[(0, used, set_idx)]\n",
    "                else:\n",
    "                    res = backtrack(0, set_idx+1, used)\n",
    "                    memo[(0, used, set_idx)] = res\n",
    "                    return res\n",
    "            \n",
    "            if (bucket, used, set_idx) in memo:\n",
    "                    return memo[(bucket, used, set_idx)]\n",
    "\n",
    "            for i in range(n):\n",
    "                if (used>>i)&1:\n",
    "                    continue\n",
    "                if bucket+nums[i]>target:\n",
    "                    continue\n",
    "                \n",
    "                used |= (1<<i)\n",
    "                bucket += nums[i]\n",
    "                if (bucket, set_idx, used) in memo:\n",
    "                    res = memo[(bucket, set_idx, used)]\n",
    "                else:\n",
    "                    res = backtrack(bucket, set_idx, used)\n",
    "                    memo[(bucket, set_idx, used)] = res\n",
    "                if res:\n",
    "                    return True\n",
    "                used ^= (1<<i)\n",
    "                bucket -= nums[i]\n",
    "            return False\n",
    "            \n",
    "        return backtrack(0, 0, used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total%k!=0:\n",
    "            return False\n",
    "        \n",
    "        each_sum = total // k\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[0] > each_sum:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        # 这样会超时\n",
    "        \n",
    "        # sub_set = [0] * k\n",
    "        # def dfs(i):\n",
    "        #     if i == n:\n",
    "        #         return True\n",
    "        #     for j in range(k):\n",
    "        #         sub_set[j] += nums[i]\n",
    "        #         if sub_set[j] <= each_sum and dfs(i+1):\n",
    "        #             return True  \n",
    "        #         sub_set[j] -= nums[i]\n",
    "        #     return False\n",
    "        # return dfs(0)\n",
    "\n",
    "        # 状态压缩\n",
    "        final = (1<<n)-1\n",
    "        @cache\n",
    "        def dfs(state, p):\n",
    "            if state == final:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if not 1<<i & state and p + nums[i] <= each_sum:\n",
    "                    if dfs(1<<i|state, (p+nums[i])%each_sum):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s % k != 0:\n",
    "            return False\n",
    "        gs = s // k \n",
    "        if max(nums) > gs:\n",
    "            return False\n",
    "        nums = sorted(nums,reverse=True)\n",
    "        n = len(nums)\n",
    "        target = 0\n",
    "        for i in range(n):\n",
    "            target |= 1 << i\n",
    "        @cache\n",
    "        def dfs(stat=0, cur_sum=0):\n",
    "            if stat == target and cur_sum == 0:\n",
    "                return True \n",
    "            for i in range(n):\n",
    "                if ((stat>>i) & 1) == 0 and nums[i] + cur_sum <= gs:\n",
    "                    new_stat = stat | (1<<i)\n",
    "                    new_sum = (nums[i]+cur_sum) % gs \n",
    "                    if dfs(new_stat, new_sum) == True:\n",
    "                        return True \n",
    "            return False\n",
    "        return dfs(0,0)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        def part(arr, curr_sum, idx):\n",
    "            if len(arr) == 0 and idx == k:\n",
    "                self.res = True\n",
    "                return\n",
    "            if (arr, curr_sum) in m:\n",
    "                return m[(arr, curr_sum)]\n",
    "            for i in range(len(arr)):\n",
    "                new_arr = tuple(arr[:i] + arr[i+1:])\n",
    "                new_sum = arr[i] + curr_sum\n",
    "                if new_sum == total:\n",
    "                    m[(new_arr, 0)] = part(new_arr, 0, idx+1)\n",
    "                elif new_sum < total:\n",
    "                    m[(new_arr, new_sum)] = part(new_arr, new_sum, idx)\n",
    "                else:\n",
    "                    pass\n",
    "\n",
    "        m = {}\n",
    "        self.res = False\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        if total % k != 0:\n",
    "            return False\n",
    "        total = total // k\n",
    "        part(tuple(nums), 0, 0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "       \n",
    "        per = sum(nums) \n",
    "        if per%k!=0:\n",
    "            return False\n",
    "        per = per//k\n",
    "        nums.sort()\n",
    "\n",
    "        if nums[-1] > per: return False\n",
    "        while nums and nums[-1] == per:\n",
    "            nums.pop()\n",
    "            k -= 1\n",
    "        N = len(nums)\n",
    "        @cache\n",
    "        def find(s, val):\n",
    "            if s == 0:\n",
    "                return True\n",
    "            for i in range(N):\n",
    "                if s & 1 << i and val + nums[i] <= per:\n",
    "                    ans = find(s ^ (1 << i), (val + nums[i])%per)\n",
    "                    if ans:\n",
    "                        return True\n",
    "            return False\n",
    "        # print(1<<N, (1<<N)-1)\n",
    "        return find((1<<N) -1, 0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # nums.sort()\n",
    "        target = sum(nums)\n",
    "        if target % k != 0:\n",
    "            return False\n",
    "        target = target // k\n",
    "\n",
    "        @cache\n",
    "        def helper(nums, res, k):\n",
    "            if k == 1:\n",
    "                return sum(nums) == target\n",
    "            if not nums:\n",
    "                return False\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                sub = res + nums[i]\n",
    "                if sub == target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), 0, k - 1):\n",
    "                        return True\n",
    "                elif sub < target:\n",
    "                    if helper(tuple(nums[:i] + nums[i + 1:]), sub, k):\n",
    "                        return True\n",
    "                # else:\n",
    "                #     return False\n",
    "            return False\n",
    "        \n",
    "        return helper(tuple(nums), 0, k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        s = sum(nums)\n",
    "\n",
    "        if s % k != 0:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        avg = s // k\n",
    "        # print(dp)\n",
    "        lim = 2 ** n - 1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state, t):\n",
    "            if state == lim:\n",
    "                return t == avg\n",
    "            if t == avg:\n",
    "                t = 0\n",
    "            for i in range(n):\n",
    "                if state & (1 << i):\n",
    "                    continue\n",
    "                if nums[i] > avg:\n",
    "                    return False\n",
    "                c = t + nums[i]\n",
    "                if c > avg:\n",
    "                    continue\n",
    "                if dfs(state | (1 << i), c):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        self.nums=nums\n",
    "        st=sum(nums)\n",
    "        if st%k!=0:\n",
    "            return False\n",
    "        self.st=st//k\n",
    "        self.k=k\n",
    "        self.res=False\n",
    "        self.ta={}\n",
    "        v=[False]*len(nums)\n",
    "        self.help(0,v,0)\n",
    "        \n",
    "        return self.res\n",
    "    def help(self, val, visited,temp):\n",
    "        if temp==self.k:\n",
    "            self.res=True\n",
    "            return\n",
    "        xt=tuple(visited+[temp])\n",
    "        if xt in self.ta:\n",
    "            return\n",
    "        self.ta[xt]=True\n",
    "        n=len(self.nums)\n",
    "        li=[]\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            if val+self.nums[i]>self.st:\n",
    "                continue\n",
    "            if val+self.nums[i]==self.st:\n",
    "                visited[i]=True\n",
    "                self.help(0,visited,temp+1)\n",
    "                visited[i]=False\n",
    "                if self.res:\n",
    "                    return\n",
    "                continue\n",
    "            visited[i]=True\n",
    "            self.help(val+self.nums[i],visited,temp)\n",
    "            visited[i]=False\n",
    "\n",
    "\n",
    "        \n",
    "                    \n",
    "                    \n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        m=sum(nums)\n",
    "        if m%k!=0:\n",
    "            return False \n",
    "        m=m//k\n",
    "        n=len(nums)\n",
    "        #use=[0]*k\n",
    "        nums.sort()\n",
    "        if nums[-1]>m:\n",
    "            return False\n",
    "        while nums and nums[-1]==m:\n",
    "            nums.pop()\n",
    "            n-=1\n",
    "            k-=1\n",
    "        if k==0:\n",
    "            return True\n",
    "        @cache\n",
    "        def dfs(x,now):\n",
    "            if x==0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i]+now>m:\n",
    "                    break\n",
    "                if x>>i &1 and dfs(x^(1<<i),(now+nums[i])%m):\n",
    "                    return True\n",
    "            return False \n",
    "        return dfs((1<<n)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        m=sum(nums)\n",
    "        if m%k!=0:\n",
    "            return False \n",
    "        m=m//k\n",
    "        n=len(nums)\n",
    "        #use=[0]*k\n",
    "        nums.sort()\n",
    "        if nums[-1]>m:\n",
    "            return False\n",
    "        while nums and nums[-1]==m:\n",
    "            nums.pop()\n",
    "            n-=1\n",
    "            k-=1\n",
    "        if k==0:\n",
    "            return True\n",
    "        find=[False]*(1<<n)\n",
    "        rem=[False]*(1<<n)\n",
    "        def dfs(x,now):\n",
    "            if find[x]:\n",
    "                return rem[x]\n",
    "            find[x]=True\n",
    "            if x==0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i]+now>m:\n",
    "                    break\n",
    "                if x>>i &1 and dfs(x^(1<<i),(now+nums[i])%m):\n",
    "                    rem[x]=True\n",
    "                    return True\n",
    "            rem[x]=False\n",
    "            return False \n",
    "        return dfs((1<<n)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\r\n",
    "        n = len(nums)\r\n",
    "        if n < k:\r\n",
    "            return False\r\n",
    "        s = sum(nums)\r\n",
    "        if s % k:\r\n",
    "            return False\r\n",
    "        nums.sort(reverse=True)\r\n",
    "        target = s // k\r\n",
    "        used_list = [0] * n\r\n",
    "        used = 0\r\n",
    "        memo = {}\r\n",
    "\r\n",
    "        def traverse(k, vol, nums, start, target, used):\r\n",
    "            nonlocal n\r\n",
    "            if k == 0:\r\n",
    "                return True\r\n",
    "            if vol == target:\r\n",
    "                return traverse(k-1, 0, nums, 0, target, used)\r\n",
    "            if used in memo:\r\n",
    "                return memo[used]\r\n",
    "            for i in range(start, n):\r\n",
    "                if used_list[i]:\r\n",
    "                    continue\r\n",
    "                if target - vol < nums[i]:\r\n",
    "                    continue\r\n",
    "                used += 2**(i-1)\r\n",
    "                used_list[i] = 1\r\n",
    "                memo[used] = traverse(k, vol+nums[i], nums, i+1, target, used)\r\n",
    "                if memo[used] == True:\r\n",
    "                    return True\r\n",
    "                used -= 2**(i-1)\r\n",
    "                used_list[i] = 0\r\n",
    "            return False\r\n",
    "\r\n",
    "        return traverse(k, 0, nums, 0, target, used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        target =sum(nums)/k\n",
    "        if target  != int(target ):\n",
    "            return False\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(state,s):\n",
    "            if len(state)==n:\n",
    "                return True\n",
    "            for j in range(n):\n",
    "                if s+nums[j]>target:\n",
    "                    break\n",
    "                if j not in state:\n",
    "                    next_state = list(state) + [j]     # 划分nums[i]\n",
    "                    next_state.sort()\n",
    "                    if dfs(tuple(next_state), (s+nums[j]) % target):    # 划分nums[i]能形成有效方案\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(tuple([]),0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % k != 0: return False\n",
    "        line = total // k\n",
    "        if any(num > line for num in nums): return False\n",
    "        \n",
    "        n = len(nums)\n",
    "        final = (1 << n) - 1\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state, cur):\n",
    "            if cur == line:\n",
    "                cur = 0\n",
    "                if state == final:\n",
    "                    return True\n",
    "            for i in range(n):\n",
    "                if (1 << i) & state == 0 and cur + nums[i] <= line:\n",
    "                    if dfs(1 << i | state, cur + nums[i]):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        sum_all = sum(nums)\n",
    "        target = sum_all // k\n",
    "        if sum_all % k or max(nums) > target:\n",
    "            return False\n",
    "        nums = sorted(nums)\n",
    "        dp = {}\n",
    "        def dfs(visited, cum, cur_k):\n",
    "            if cur_k == k:\n",
    "                return True\n",
    "            if not dp.get((visited, cur_k), None) == None:\n",
    "                return dp.get((visited, cur_k))\n",
    "            res = False\n",
    "            for i in range(len(nums)):\n",
    "                if (visited >> i) & 1:\n",
    "                    continue\n",
    "                if cum + nums[i] == target:\n",
    "                    if dfs(visited | (1 << i), 0, cur_k + 1):\n",
    "                        res = True\n",
    "                        break\n",
    "                elif cum + nums[i] < target:\n",
    "                    if dfs(visited | (1 << i), cum + nums[i], cur_k):\n",
    "                        res = True\n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            dp[(visited, cur_k)] = res\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, 0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        sumed = sum(nums)\n",
    "        if sumed % k != 0:\n",
    "            return False\n",
    "        \n",
    "        target = sumed // k \n",
    "        n = len(nums)\n",
    "        memo = {}\n",
    "        used = 0\n",
    "\n",
    "        def backtrack(nums, start, kk, bucket, target, used):\n",
    "            nonlocal n, memo, k\n",
    "            if kk == k:\n",
    "                return True\n",
    "            if used in memo:\n",
    "                return memo[used]\n",
    "            \n",
    "            if bucket == target:\n",
    "                flag = backtrack(nums, 0, kk+1, 0, target, used)\n",
    "                if flag:\n",
    "                    memo[used] = flag\n",
    "                    return flag\n",
    "                \n",
    "            for i in range(start, n):\n",
    "                if used & (1 << i) > 0:\n",
    "                    continue\n",
    "                if bucket + nums[i] <= target:\n",
    "                    bucket += nums[i]\n",
    "                    used |= (1 << i)\n",
    "                    flag = backtrack(nums, start+1, kk, bucket, target, used)\n",
    "                    memo[used] = flag\n",
    "                    if flag:\n",
    "                        return True\n",
    "                    used ^= (1 << i)\n",
    "                    bucket -= nums[i]\n",
    "            return False\n",
    "        \n",
    "        return backtrack(nums, 0, 0, 0, target, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        cache = dict()\n",
    "        def dfs(state, cur_sum):\n",
    "            if (state, cur_sum) in cache:\n",
    "                return cache[(state, cur_sum)] \n",
    "            if state == (1<<len(nums))-1: \n",
    "                return True   \n",
    "            for j in range(len(nums)):\n",
    "                if state & (1<<j) == 0:\n",
    "                    if cur_sum + nums[j] > target:\n",
    "                        break  \n",
    "                    if dfs(state+(1<<j), (cur_sum+nums[j]) % target):\n",
    "                        cache[(state+(1<<j), (cur_sum+nums[j])%target)] = True  \n",
    "                        return True  \n",
    "            cache[(state, cur_sum)] = False  \n",
    "            return False \n",
    "        total = sum(nums) \n",
    "        if total % k != 0:\n",
    "            return False  \n",
    "        target = total // k  \n",
    "        nums.sort()  \n",
    "        if nums[-1] > target:\n",
    "            return False  \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        \n",
    "        # @cache\n",
    "        cache = dict()      # 手动实现记忆化单元\n",
    "\n",
    "        def dfs(state, summ):\n",
    "\n",
    "            if (state, summ) in cache:      # 从记忆中直接读取\n",
    "                return cache[(state, summ)]\n",
    "            \n",
    "            if state == (1<<n) - 1:         # 所有整数均已划分，结束递归，并返回True\n",
    "                # cache[(state, summ)] = True\n",
    "                return True\n",
    "            \n",
    "            for j in range(n):\n",
    "                if summ + nums[j] > target: # nums已升序排列，当前数字不行，后续肯定也不行\n",
    "                    break\n",
    "                if state & (1<<j) == 0:             # nums[i]暂未被划分\n",
    "                    next_state = state + (1<<j)     # 划分nums[i]\n",
    "                    if dfs(next_state, (summ+nums[j]) % target):    # 划分nums[i]能形成有效方案\n",
    "                        cache[(state, summ)] = True     # 加入记忆化单元【避免后续重复计算】\n",
    "                        return True\n",
    "            \n",
    "            cache[(state, summ)] = False                # 加入记忆化单元【避免后续重复计算】\n",
    "            return False\n",
    "        \n",
    "        total = sum(nums)\n",
    "        if total % k != 0:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        target = total // k     # 目标非空子集的和\n",
    "        nums.sort()             # 升序排列\n",
    "        if nums[-1] > target:   # 最大值超过目标子集和，无法划分\n",
    "            return False\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        all = sum(nums)\n",
    "        if all % k:\n",
    "            return False\n",
    "        per = all // k\n",
    "        nums.sort()  # 方便下面剪枝\n",
    "        if nums[-1] > per:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i] + p > per:\n",
    "                    break\n",
    "                if s >> i & 1 and dfs(s ^ (1 << i), (p + nums[i]) % per):  # p + nums[i] 等于 per 时置为 0\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs((1 << n) - 1, 0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        tot = sum(nums)\n",
    "        if tot % k : return False\n",
    "        t, n = tot // k, len(nums)\n",
    "        nums.sort()\n",
    "        if nums[-1] > t: return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0: return True\n",
    "            for i in range(n):\n",
    "                if p + nums[i] > t: break\n",
    "                if s >> i & 1 and dfs(s ^ (1 << i), (p + nums[i]) % t):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs((1 << n) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        all=sum(nums)\n",
    "        if all%k:\n",
    "            return False\n",
    "        per=all//k\n",
    "        nums.sort()\n",
    "        if nums[-1]>per:\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(s,now):\n",
    "            print(now)\n",
    "            if s==0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i]+now>per:\n",
    "                    break\n",
    "                if s>>i&1 and dfs(s^(1<<i),(now+nums[i])%per):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs((1<<n)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < k:\n",
    "            return False\n",
    "        arr_sum = sum(nums)\n",
    "        if arr_sum % k != 0:\n",
    "            return False\n",
    "        subset_sum = arr_sum // k\n",
    "        visited = ['0'] * n\n",
    "        nums.sort(reverse=True)\n",
    "        memo = dict()\n",
    "        def partition(cur_sum, count, idx):\n",
    "            if count == k - 1:\n",
    "                return True\n",
    "            if cur_sum > subset_sum:\n",
    "                return False\n",
    "            flag = ''.join(visited)\n",
    "            if flag in memo:\n",
    "                return memo[flag]\n",
    "            if cur_sum == subset_sum:\n",
    "                memo[flag] = partition(0, count + 1, 0)\n",
    "                return memo[flag]\n",
    "            for i in range(idx, n):\n",
    "                if visited[i] == '0':\n",
    "                    visited[i] = '1'\n",
    "                    if partition(cur_sum + nums[i], count, i+1):\n",
    "                        return True\n",
    "                    visited[i] = '0'\n",
    "            memo[flag] = False\n",
    "            return False\n",
    "        return partition(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % k:\n",
    "            return False\n",
    "        pre = total / k \n",
    "        nums.sort()\n",
    "        if nums[-1] > pre:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0 and p == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i] + p > pre:\n",
    "                    break\n",
    "                elif s>>i & 1 and dfs(s^(1<<i), (nums[i]+p)%pre):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs((1<<n)-1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isInteger(target):\n",
    "    return target%1==0\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        target = sum(nums)/k\n",
    "        if not isInteger(target):\n",
    "            return False\n",
    "\n",
    "        nums.sort()\n",
    "        if nums[-1]>target:\n",
    "            return False\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache  # 记忆化单元\n",
    "        def dfs(state, summ):\n",
    "            if state == (1<<n)-1:                 # 所有整数均已划分，结束递归，并返回True\n",
    "                return True\n",
    "            for j in range(n):\n",
    "                if summ + nums[j] > target:         # nums已升序排列，当前数字不行，后续肯定也不行\n",
    "                    break\n",
    "                if state & (1<<j) == 0:             # nums[i]暂未被划分\n",
    "                    next_state = state + (1<<j)     # 划分nums[i]\n",
    "                    if dfs(next_state, (summ+nums[j]) % target):    # 划分nums[i]能形成有效方案\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum % k != 0:\n",
    "            return False\n",
    "        \n",
    "        self.target_sum = total_sum // k\n",
    "        self.used = [False] * len(nums)\n",
    "        self.memo = {}\n",
    "        return self.backtrack(nums, k, 0, 0)\n",
    "\n",
    "    def backtrack(self, nums, k, track_sum, start):\n",
    "        if k == 0:\n",
    "            return True\n",
    "        \n",
    "        if track_sum == self.target_sum:\n",
    "            return self.backtrack(nums, k - 1, 0, 0)\n",
    "\n",
    "        if (start, track_sum, tuple(self.used)) in self.memo:\n",
    "            return self.memo[(start, track_sum, tuple(self.used))]\n",
    "        \n",
    "        for i in range(start, len(nums)):\n",
    "            if not self.used[i] and track_sum + nums[i] <= self.target_sum:\n",
    "                self.used[i] = True\n",
    "                if self.backtrack(nums, k, track_sum + nums[i], i + 1):\n",
    "                    self.memo[(start, track_sum, tuple(self.used))] = True\n",
    "                    return True\n",
    "                self.used[i] = False\n",
    "\n",
    "        self.memo[(start, track_sum, tuple(self.used))] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        msum = sum(nums)\n",
    "        if msum%k!=0:\n",
    "            return False\n",
    "        per = msum/k\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        if nums[-1]>per:\n",
    "            return False\n",
    "        @cache\n",
    "        def sub(s,p):\n",
    "            if s==0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if s >> i & 1:\n",
    "                    if p + nums[i]>per:\n",
    "                        continue\n",
    "                    if sub(s^ (1 << i), (p+nums[i])%per):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return sub((1<<n)-1,0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 官方解法1\n",
    "        all = sum(nums)\n",
    "        if all % k != 0:\n",
    "            return False\n",
    "        target = all / k \n",
    "        nums.sort()\n",
    "        if nums[-1] > target:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0:\n",
    "                return True \n",
    "            for i in range(n):\n",
    "                if nums[i] + p > target:  # 小的都已经不能通过了 后面就更不可能了 遍历结束\n",
    "                    break\n",
    "                if s >> i & 1 and dfs(s ^ (1 << i), (p + nums[i]) % target):\n",
    "                    return True \n",
    "            return False\n",
    "        return dfs((1 << n) - 1, 0)  # s保存每一位的状态 是否被选过\n",
    "\n",
    "\n",
    "\n",
    "        # 以下是回溯的两个视角\n",
    "        # 解法2 桶的视角 时间复杂度o(k*2^n)\n",
    "        # n = len(nums)\n",
    "        # sumNum = sum(nums)\n",
    "        # nums.sort(reverse = True)\n",
    "        # target = sumNum / k \n",
    "\n",
    "        # if nums[0] > target:\n",
    "        #     return False\n",
    "        # if sumNum % k != 0:\n",
    "        #     return False\n",
    "        \n",
    "\n",
    "        \n",
    "        # # used = [False] * n \n",
    "        # used = 0\n",
    "\n",
    "        # # 存储当前used状态下的结果   相同状态下可进行记忆化搜索\n",
    "        # memo = {}\n",
    "\n",
    "        \n",
    "        # def dfs(k, bucket, nums, start, used, target):\n",
    "        #     if k == 0: #所有桶都装完了\n",
    "        #         return True\n",
    "\n",
    "        #     # state = \"\".join(str(used))  # 转化为字符串作为memo的键\n",
    "\n",
    "        #     if bucket == target:\n",
    "        #         res = dfs(k-1, 0, nums, 0, used, target)\n",
    "        #         memo[used] = res  # 当前状态以及对应的结果\n",
    "        #         return res \n",
    "            \n",
    "        #     # 记忆化搜索\n",
    "        #     if used in memo.keys():\n",
    "        #         return memo.get(used)\n",
    "\n",
    "        #     # 从start开始 探查有效的nums[i]装入当前桶中\n",
    "        #     for i in range(start, n):\n",
    "        #         if (used >> i) & 1 == 1:\n",
    "        #             continue\n",
    "        #         if nums[i] + bucket > target:\n",
    "        #             continue\n",
    "\n",
    "        #         # used[i] = True\n",
    "        #         used |= 1 << i  # 将第 i个位置为1（或运算将第i位变为1）\n",
    "        #         bucket += nums[i]\n",
    "        #         # 递归穷举下一个数是否装入当前桶中\n",
    "        #         if (dfs(k, bucket, nums, i+1, used, target)):\n",
    "        #             return True\n",
    "        #         # used[i] = False\n",
    "        #         used ^= 1 << i # 使用异或运算将第i位恢复为0（相同元素的异或结果为0）\n",
    "        #         bucket -= nums[i]\n",
    "        #     # 穷举了所有数字 当前桶都无法装满\n",
    "        #     return False\n",
    "        # return dfs(k, 0, nums, 0, used, target)\n",
    "\n",
    "        # 解法1 数字视角 排序优化后依然超时 时间复杂度o(k ^ n)\n",
    "        # n = len(nums)\n",
    "        # nums.sort(reverse = True)   # 使得剪枝部分过滤掉尽可能多 从而递归次数少\n",
    "        # sumNum = sum(nums)\n",
    "        # if n < k:\n",
    "        #     return False\n",
    "        # if sumNum % k != 0:\n",
    "        #     return False\n",
    "\n",
    "\n",
    "        # buckets = [0] * k \n",
    "        # target = sumNum / k \n",
    "\n",
    "        # # 选择数\n",
    "        # def dfs(nums, i, buckets, target):\n",
    "        #     if i == n:\n",
    "        #         # 检查桶内数字之和\n",
    "        #         for j in range(k):\n",
    "        #             if buckets[j] != target:\n",
    "        #                 return False\n",
    "        #         return  True \n",
    "\n",
    "        #     # 选择桶\n",
    "        #     for j in range(k):\n",
    "        #         # 剪枝\n",
    "        #         if buckets[j] + nums[i] > target:\n",
    "        #             continue\n",
    "        #         # 将nums[i]放入第j个桶\n",
    "        #         buckets[j] += nums[i]\n",
    "        #         # 选择将nums[i+1]放入的桶\n",
    "        #         if dfs(nums, i+1, buckets, target):\n",
    "        #             return True\n",
    "        #         buckets[j] -= nums[i]\n",
    "        #     return False\n",
    "\n",
    "        # return dfs(nums, 0, buckets, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        #状态压缩+位运算+记忆化搜索\n",
    "        #非常经典的题目\n",
    "        total=sum(nums)\n",
    "        target=total/k\n",
    "        if target%1!=0:\n",
    "            return False\n",
    "        #方便剪枝\n",
    "        nums.sort()\n",
    "        if nums[-1]>target:\n",
    "            return False\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(pos,val):\n",
    "            if pos==0: return True\n",
    "            for i in range(n):\n",
    "                if val+nums[i]>target: break\n",
    "                if pos&(1<<i) and dfs(pos^(1<<i),(val+nums[i])%target):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs((1<<n)-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        all_sum = sum(nums)\n",
    "        if all_sum%k!=0:return False\n",
    "        per_sum = all_sum//k\n",
    "        nums.sort()\n",
    "        if nums[-1]>per_sum:return False\n",
    "        n = len(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(bucket,every_sum):\n",
    "            if bucket== \"0\"*n and every_sum == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if every_sum+nums[i]>per_sum:break\n",
    "                bucket = list(bucket)\n",
    "                if bucket[i] == \"1\":\n",
    "                    bucket[i] = \"0\"\n",
    "                    if dfs(\"\".join(bucket),(every_sum+nums[i])%per_sum):return True\n",
    "                    bucket[i] = \"1\"\n",
    "            return False\n",
    "        return dfs(\"1\"*n,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 桶太多\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        \n",
    "        # 元素和不可整除\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums % k != 0:\n",
    "            return False\n",
    "        \n",
    "        per_target = sum_nums // k \n",
    "        nums.sort() # 先排序方便剪枝\n",
    "        if nums[-1] > per_target:\n",
    "            # 单元素大于桶容量\n",
    "            return False\n",
    "\n",
    "        n = len(nums)\n",
    "        valid = (1 << n) - 1  # 位图表示可用数组集合，全1\n",
    "        \n",
    "        @cache\n",
    "        def backtrack(valid, cur_sum):\n",
    "            if valid == 0:\n",
    "                return True\n",
    "            if cur_sum == per_target:\n",
    "                return backtrack(valid, 0)\n",
    "            for i in range(n):\n",
    "                if nums[i] + cur_sum > per_target:\n",
    "                    break\n",
    "                if valid >> i & 1 and backtrack(valid ^ (1 << i), (cur_sum + nums[i])):  # cur_sum + nums[i] 等于 per 时置为 0\n",
    "                    return True\n",
    "            return False\n",
    "        return backtrack(valid, 0)\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        # 桶太多\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        \n",
    "        # 元素和不可整除\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums % k != 0:\n",
    "            return False\n",
    "        \n",
    "        per_target = sum_nums // k \n",
    "        nums.sort() # 先排序方便剪枝\n",
    "        if nums[-1] > per_target:\n",
    "            # 单元素大于桶容量\n",
    "            return False\n",
    "\n",
    "        n = len(nums)\n",
    "        valid = (1 << n) - 1  # 位图表示可用数组集合，全1\n",
    "        \n",
    "        # cache 类似于 memo\n",
    "        @cache\n",
    "        def backtrack(valid, cur_sum):\n",
    "            if valid == 0:\n",
    "                # 所有数字用完\n",
    "                return True\n",
    "            if cur_sum == per_target:\n",
    "                # 该桶装完\n",
    "                return backtrack(valid, 0)\n",
    "\n",
    "            for i in range(n):\n",
    "                if valid >> i & 1 != 1:\n",
    "                    # 数字已分配，跳过\n",
    "                    continue\n",
    "                if nums[i] + cur_sum > per_target:\n",
    "                    # 由于已排序，当前元素会超出容量，则之后的元素也会\n",
    "                    break\n",
    "                \n",
    "                # 做选择\n",
    "                valid = valid ^ (1 << i)\n",
    "                # 递归装入桶\n",
    "                if backtrack(valid, cur_sum + nums[i]):\n",
    "                    return True\n",
    "                # 撤销选择\n",
    "                valid = valid | (1 << i)\n",
    "            # 穷举完毕\n",
    "            return False\n",
    "        return backtrack(valid, 0)\n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        tot = sum(nums)\n",
    "        if tot % k > 0: return False\n",
    "\n",
    "        each = tot // k\n",
    "        nums.sort()\n",
    "        if nums[-1] > each: return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(state, p, left):\n",
    "            if left == 0:\n",
    "                return True\n",
    "            for j in range(n):\n",
    "                if nums[j] + p > each:\n",
    "                    break\n",
    "                if state[j] == '1' and dfs(state[:j]+'0'+state[(j+1):], (nums[j] + p)%each, left-1):  # 如果=each置为0\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(\"1\"*n, 0, n)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        t = sum(nums)\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        if t % k:\n",
    "            return False\n",
    "        L = t // k\n",
    "        if nums[-1] > L:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(s,p):\n",
    "            if s == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if nums[i] + p > L:\n",
    "                    continue\n",
    "                if s >> i & 1 and dfs(s ^ (1 << i),(p + nums[i]) % L):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        return dfs((1 << n) - 1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums, k: int) -> bool:\n",
    "        if sum(nums) % k:\n",
    "            return False\n",
    "        ssum = sum(nums) // k\n",
    "        print(ssum)\n",
    "        n = len(nums)\n",
    "        self.used = [False] * n\n",
    "        self.memo = {}\n",
    "        def hash(used):\n",
    "            return ''.join(['1' if i else '0' for i in used])\n",
    "\n",
    "        def dfs(cur, k, start):\n",
    "            if k == 0:\n",
    "                return True\n",
    "            if cur == ssum:\n",
    "                res = dfs(0, k-1, 0)\n",
    "                self.memo[hash(self.used)] = res\n",
    "                return res\n",
    "            if hash(self.used) in self.memo:\n",
    "                return self.memo[hash(self.used)]\n",
    "            for i in range(start, len(nums)):\n",
    "                num = nums[i]\n",
    "            # for i, num in enumerate(nums):\n",
    "                if num + cur > ssum or self.used[i]:\n",
    "                    continue\n",
    "                self.used[i] = True\n",
    "                if dfs(cur + num, k, i+1):\n",
    "                    self.memo[hash(self.used)] = True\n",
    "                    return True\n",
    "                self.used[i] = False\n",
    "            self.memo[hash(self.used)] = False\n",
    "            return False\n",
    "        return dfs(0, k, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        nums.sort(reverse=True)  # 从大到小枚举，剪枝\n",
    "        target = sum(nums) // k\n",
    "        if target * k != sum(nums): return False\n",
    "        if max(nums) > target: return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(k, cur, start, used):\n",
    "            if k == 0:\n",
    "                return True\n",
    "            if cur == target:\n",
    "                return dfs(k-1, 0, 0, used)\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                if (used >> i) & 1 == 1 or nums[i] + cur > target:\n",
    "                    continue\n",
    "                if dfs(k, cur + nums[i], start+1, used | (1 << i)):\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(k, 0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        n=len(nums)\n",
    "        total=sum(nums)\n",
    "        nums.sort()\n",
    "        if total%k!=0:\n",
    "            return False\n",
    "        target=total//k\n",
    "        if nums[-1]>target:\n",
    "            return False\n",
    "        idx='1'*n\n",
    "        @cache      \n",
    "        def dfs(idx, p):\n",
    "            if int(idx)==0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                if p+nums[i]>target:\n",
    "                    break\n",
    "                if idx[i]=='1':\n",
    "                    newidx=idx[0:i]+'0'+idx[i+1:n]\n",
    "                    if dfs(newidx, (p+nums[i])%target):\n",
    "                        return True      \n",
    "            return False\n",
    "        return dfs(idx,0)\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums, k):\n",
    "        q = sum(nums)\n",
    "        L = len(nums)\n",
    "        if q % k != 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        @lru_cache(None)\n",
    "        def f(vis, i, k, now, v, lf):\n",
    "            #print(k, now, v, bin(vis), nums, lf)\n",
    "            if now == v and k == 1:\n",
    "                return True\n",
    "            else:\n",
    "                if now == v:\n",
    "                    now = 0\n",
    "                    k -= 1\n",
    "                    i = 0\n",
    "                if lf < k: return False\n",
    "                for j in range(i, L):\n",
    "                    if (vis >> j) & 1 != 1:\n",
    "                        ui = now + nums[j]\n",
    "                        if ui < v:\n",
    "                            if f(vis | (1 << j), j + 1, k, ui, v, lf - 1):\n",
    "                                return True\n",
    "                        elif ui == v:\n",
    "                            return f(vis | (1 << j), j + 1, k, ui, v, lf - 1)\n",
    "                        else:\n",
    "                            return False\n",
    "            return False\n",
    "        return f(0, 0, k, 0, q//k, L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        # 能否，有返回值？\n",
    "\n",
    "        if sum(nums) % k:   # 不能整除\n",
    "            return False\n",
    "        \n",
    "        part = sum(nums) // k    # 单个子集和\n",
    "\n",
    "        for n in nums:           # 剪枝。单个元素不能超过子集和\n",
    "            if n > part:\n",
    "                return False\n",
    "\n",
    "        ### 全排列方式，枚举每个未使用的元素，加入当前的子集\n",
    "        mems = set()\n",
    "\n",
    "        used = ['0' for i in range(len(nums))]\n",
    "\n",
    "        def dfs(i, acc): # 第i个子集，当前和\n",
    "            \n",
    "            if acc > part:      # 当前子集和超目标\n",
    "                return False\n",
    "            \n",
    "            if acc == part:     # 下一个子集\n",
    "                return dfs(i+1, 0)\n",
    "\n",
    "            if i == k:\n",
    "                return True\n",
    "\n",
    "            status = ''.join(used) + '_' + chr(i) + '_' + chr(acc)\n",
    "\n",
    "            if status in mems:\n",
    "                return False\n",
    "            \n",
    "            mems.add(status)\n",
    "\n",
    "            for j in range(len(nums)):\n",
    "                if used[j] == '1':             # 跳过以做选择\n",
    "                    continue\n",
    "\n",
    "                used[j] = '1'\n",
    "                if dfs(i, acc+nums[j]): # 后面有情况是True，那就是True\n",
    "                    return True\n",
    "                used[j] = '0'         # 回溯\n",
    "\n",
    "            return False\n",
    "\n",
    "        return dfs(0, 0)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, a: List[int], k: int) -> bool:\n",
    "        n, s = len(a), sum(a)\n",
    "        if s % k: return False\n",
    "        m = s // k\n",
    "        vis, f, c = [False] * (1 << n), [False] * (1 << n), [0] * (1 << n)\n",
    "        for i in range(1, 1 << n):\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    c[i] += a[j]\n",
    "        alls = [mask for mask in range(1 << n) if c[mask] == m]\n",
    "        def dp(mask):\n",
    "            if mask == 0: return True\n",
    "            if vis[mask]: return f[mask]\n",
    "            res = False\n",
    "            for u in alls:\n",
    "                if u > mask: break\n",
    "                if u | mask == mask and dp(mask - u):\n",
    "                    res = True\n",
    "                    break\n",
    "            f[mask], vis[mask] = res, True\n",
    "            return f[mask]\n",
    "\n",
    "        return dp((1 << n) - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        n = len(nums)\n",
    "    \n",
    "        total_array_sum = sum(nums)\n",
    "        \n",
    "        # If the total sum is not divisible by k, we can't make subsets.\n",
    "        if total_array_sum % k != 0:\n",
    "            return False\n",
    "\n",
    "        target_sum = total_array_sum // k\n",
    "\n",
    "        # Sort in decreasing order.\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        taken = ['0'] * n\n",
    "        \n",
    "        memo = {}\n",
    "        \n",
    "        def backtrack(index, count, curr_sum):\n",
    "            n = len(nums)\n",
    "            \n",
    "            taken_str = ''.join(taken)\n",
    "      \n",
    "            # We made k - 1 subsets with target sum and the last subset will also have target sum.\n",
    "            if count == k - 1:\n",
    "                return True\n",
    "            \n",
    "            # No need to proceed further.\n",
    "            if curr_sum > target_sum:\n",
    "                return False\n",
    "            \n",
    "            # If we have already computed the current combination.\n",
    "            if taken_str in memo:\n",
    "                return memo[taken_str]\n",
    "            \n",
    "            # When curr sum reaches target then one subset is made.\n",
    "            # Increment count and reset current sum.\n",
    "            if curr_sum == target_sum:\n",
    "                memo[taken_str] = backtrack(0, count + 1, 0)\n",
    "                return memo[taken_str]\n",
    "            \n",
    "            # Try not picked elements to make some combinations.\n",
    "            for j in range(index, n):\n",
    "                if taken[j] == '0':\n",
    "                    # Include this element in current subset.\n",
    "                    taken[j] = '1'\n",
    "                    # If using current jth element in this subset leads to make all valid subsets.\n",
    "                    if backtrack(j + 1, count, curr_sum + nums[j]):\n",
    "                        return True\n",
    "                    # Backtrack step.\n",
    "                    taken[j] = '0'\n",
    "                    \n",
    "            # We were not able to make a valid combination after picking \n",
    "            # each element from the array, hence we can't make k subsets.\n",
    "            memo[taken_str] = False\n",
    "            return memo[taken_str] \n",
    "        \n",
    "        return backtrack(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        all = sum(nums)\n",
    "        if all % k:\n",
    "            return False\n",
    "        per = all // k\n",
    "        if not nums <= [per]*len(nums):\n",
    "            return False\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        # s was nums visited state\n",
    "        # 11 ->3 measn len was 2 and all can using\n",
    "        # 00 ->0 means len was 2 and all be visited\n",
    "        # p was persent bucket data\n",
    "        @cache\n",
    "        def dfs(s, p):\n",
    "            if s == 0:\n",
    "                return True\n",
    "            for i in range(n):\n",
    "                # \n",
    "                if nums[i] + p > per:\n",
    "                    break\n",
    "                if not (s >> i & 1):\n",
    "                    continue\n",
    "                # if nums[i] not be used and dfs sub all was true\n",
    "                # then return true\n",
    "                # there no need bucket to save result\n",
    "                # all munber was be calculated can delive to k part\n",
    "                # so we only need keep to got per size bucket and tagged nums\n",
    "                if dfs(s^(1 << i), (p + nums[i]) % per): \n",
    "                    return True\n",
    "            return False\n",
    "            # (1<<n)-1 all points was 1 means all points can using\n",
    "        return dfs((1 << n) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        sums = sum(nums)\n",
    "        n = len(nums)\n",
    "        if sums % k != 0:\n",
    "            return False\n",
    "        width = sums // k\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(mask: int, done: int) -> bool:\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                if not (mask & (1 << i)):\n",
    "                    total += nums[i]\n",
    "            \n",
    "            if total > 0 and total % width == 0:\n",
    "                done += 1\n",
    "            \n",
    "            if done == k - 1:\n",
    "                return True\n",
    "            \n",
    "            c = total // width\n",
    "            rem = width * (c + 1) - total\n",
    "\n",
    "            for i in range(n):\n",
    "                if nums[i] <= rem and (mask & (1 << i)):\n",
    "                    if dfs(mask ^ (1 << i), done):\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        return dfs((1 << n) - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        tot = sum(nums)\n",
    "        if tot % k != 0: return False\n",
    "        target, n = tot // k, len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask, p):\n",
    "            if mask == (1 << n) - 1: \n",
    "                return p == 0\n",
    "            for i in range(n):\n",
    "                if p + nums[i] > target: break\n",
    "                if (mask >> i) & 1: continue\n",
    "                if dfs(mask | (1 << i), (p + nums[i]) % target):\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        sm,n= sum(nums),len(nums)\n",
    "        nums.sort()\n",
    "        if sm%k!=0:\n",
    "            return False\n",
    "        p = sm//k\n",
    "        @cache\n",
    "        def dfs(sta,cur) -> bool:\n",
    "            if sta == ((1<<n)-1):\n",
    "                return True\n",
    "            for i in range(0,n):\n",
    "                if nums[i]+cur>p:\n",
    "                    break\n",
    "                if (sta&(1<<i))==0 and dfs(sta|(1<<i),(cur+nums[i])%p):#没选过.\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(state, t):\n",
    "            if state == mask:\n",
    "                return True\n",
    "            for i, v in enumerate(nums):\n",
    "                if (state >> i) & 1:\n",
    "                    continue\n",
    "                if t + v > s:\n",
    "                    break\n",
    "                if dfs(state | 1 << i, (t + v) % s):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        s, mod = divmod(sum(nums), k)\n",
    "        if mod:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        mask = (1 << len(nums)) - 1\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "#         # 桶选球\n",
    "#         sums=sum(nums)\n",
    "#         if sums%k!=0:\n",
    "#             return False\n",
    "#         nums.sort(reverse=True)\n",
    "#         per=sums//k\n",
    "#         if nums[-1]>per:\n",
    "#             return False\n",
    "#         used=[False]*len(nums)\n",
    "#         def divide_set(cnt,start,cur_sum):\n",
    "#             if cnt==0:\n",
    "#                 return True\n",
    "#             if cur_sum==per:\n",
    "#                 return divide_set(cnt-1,0,0)\n",
    "             \n",
    "#             for i in range(start,len(nums)):\n",
    "#                 if used[i] or cur_sum+nums[i]>per:\n",
    "#                     continue\n",
    "#                 used[i]=True\n",
    "#                 if divide_set(cnt,i+1,cur_sum+nums[i]):\n",
    "#                     return True\n",
    "#                 used[i]=False\n",
    "#             if cur_sum == 0:\n",
    "#                 return False \n",
    "\n",
    "#             return False\n",
    "#         return divide_set(k,0,0)\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "        @cache\n",
    "        def dfs(state, t):\n",
    "            if state == mask:\n",
    "                return True\n",
    "            for i, v in enumerate(nums):\n",
    "                if (state >> i) & 1:\n",
    "                    continue\n",
    "                if t + v > s:\n",
    "                    break\n",
    "                if dfs(state | 1 << i, (t + v) % s):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        s, mod = divmod(sum(nums), k)\n",
    "        if mod:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        mask = (1 << len(nums)) - 1\n",
    "        return dfs(0, 0)\n",
    "\n",
    "\n",
    "# # 球选捅\n",
    "# class Solution:\n",
    "#     def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "#         def dfs(i): # i是nums的idx\n",
    "#             if i == len(nums):\n",
    "#                 return True\n",
    "#             for j in range(k):\n",
    "#                 if j and cur[j] == cur[j - 1]:\n",
    "#                     continue\n",
    "#                 cur[j] += nums[i]\n",
    "#                 if cur[j] <= s and dfs(i + 1):\n",
    "#                     return True\n",
    "#                 cur[j] -= nums[i]\n",
    "#             return False\n",
    "\n",
    "#         s, mod = divmod(sum(nums), k)\n",
    "#         if mod:\n",
    "#             return False\n",
    "#         cur = [0] * k\n",
    "#         nums.sort(reverse=True)\n",
    "#         return dfs(0)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:\n",
    "         #idx代表第idx个数\n",
    "        @cache\n",
    "        def backtrack(state,t):\n",
    "            if state == mask:\n",
    "                return True\n",
    "            for i,v in enumerate(nums):\n",
    "                if (state >> i) & 1:      \n",
    "                    continue\n",
    "                if t + v > target:\n",
    "                    break\n",
    "                if backtrack(state | 1 << i,(t + v) % target):\n",
    "                    return True\n",
    "            return False\n",
    "        if k > len(nums):\n",
    "            return False\n",
    "        sum = 0\n",
    "        for n in nums:\n",
    "            sum += n\n",
    "        if sum % k != 0:\n",
    "            return False\n",
    "        target = sum // k\n",
    "        # cur = [0] * k\n",
    "        nums.sort()\n",
    "        mask = (1 << len(nums)) - 1\n",
    "        return backtrack(0,0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
